An article on the Tree class hierarchy is scheduled to appear in the September or October 1993 issue of The Smalltalk Report.
Tree filein version 1.1. ''LW'' suffix in class name is explained under ''Naming conventions'' below.
Changes from version 1.0: Increase the flexibility of the tree inheritance hierarchy and the possibilities for subclassing it by making TreeLW an abstract class and making all instance variables optional. There are now more combinations of possible instance variables and therefore more subclasses. Update the test suite to relect these changes.
Copyright (c) 1993 by Bruce Samuelson. Released to the public domain. Permission is granted to place this in Smalltalk archives such as Illinois, Manchester, and ParcBench. For use with ParcPlace VisualWorks 1.0 and ObjectWorks 4.1.
The filein includes the following material:
13 tree classes: TreeLW and 12 subclasses
2 testing classes: TesterLW and TesterForTreesLW
13 testing subclasses containing test suites for the 13 tree classes
supporting methods added to ParcPlace classes.
The filein represents work in progress. If you use it, send bug reports, suggestions, modifications, and additions to bruce@utafll.uta.edu (uta eff ell ell) or bruce@ling.uta.edu. If you modify it, please document who wrote which part.
Naming conventions: I am using this distasteful scheme until Smalltalk supports better name space partitioning. (1) Class names: I add the ''LW'' suffix to all my class names to reduce the risk of collisions with other people''s classes. It stands for Linguist''s Workbench, a set of linguistic tools I''m developing. (2) Method names: When I add a utility method to a standard ParcPlace class such as Object or String, I add the ''LW'' suffix to its name for the same reason. Exceptions are methods that need to be used polymorphically with ParcPlace methods, methods with binary selectors, and those which for aesthetic reasons would be too ugly with this suffix. (3) Protocol names: When I add a utility method to a ParcPlace class, I put the method in a protocol with an ''lw'' prefix (usually ''lw extensions''). This distinguishes it from ParcPlace methods. Although my browser includes tools for supporting these naming conventions, the fileout does not include the browser tools.
You''ll get a list of the ''lw...'' protocols when you file in the code. Keep track of this list for future reference. Next time you build a new image, you''ll need to file out these protocols. The classes containing these new protocols are: Array, Character, Collection, InternalStream, Object, OrderedCollection class, OrderedCollection, PositionableStream, SequenceableCollection class, SequenceableCollection, Set, SortedCollection, String class, String.
(B) NORMAL CLASS COMMENTS
TreeLW is an abstract class with no instance variables. It represents a hierarchical structure whose intermediate nodes are called branches and whose terminal nodes are called leaves.
TreeLW forms the root of an inheritance hierarchy for several tree classes. They are application neutral and are analogous to the upper levels of the Collection hierarchy. The design goal is that they be robust and flexible enough to be reusable in a range of applications, either directly or as anchors for application specific subclasses, and that they be reasonably efficient in space and time.
The strategies for achieving this goal are to (1) offer Tester classes that validate the methods in the tree classes, (2) validate selected arguments passed by clients of tree services, (3) place support for each service at the highest possible level in the inheritance hierarchy, (4) maximize polymorphic use of services, (5) minimize code duplication, (6) introduce instance variables at the lowest possible level in the hierarchy, (7) minimize direct access to instance variables, and (8) offer flexibility in the way subtrees are represented.
Most of these strategies are object oriented versions of motherhood and apple pie. However, it takes some discipline to apply them to the design of tree classes in Smalltalk. Trees as conceived here are most naturally represented by multiple inheritance while Smalltalk only supports single inheritance. Let''s consider each strategy in turn.
(1) Class validation suite
TreeLW and its subclasses can be validated by evaluating the code below and observing the results in the SystemTranscript. TesterForTreesLW is a common superclass for the tree validation suites. The suites contain examples of how to use trees properly and of programming errors. Their methods can be cross referenced using ''senders'' and ''implementors'' in the system browser.
TesterForTreesLW new runAllSubclasses.
(2) Argument validation
When a tree client sends a message that creates or modifies a tree, its arguments get validated by methods in the ''private validating'' protocol. These catch most errors before they can cause trouble and provide a clearer explanation of the error than would be possible if it went undetected until later in the processing. Although the performance penalty is relatively modest, application subclasses may override the validations with no-ops if they need to minimize the penalty.
(3-5) High level, polymorphic services with minimal code duplication
Most methods are defined in TreeLW itself and do not need to be redefined by subclasses. This minimizes code duplication. An example is the definition of a tree''s root. If the tree maintains a superTree pointer, the root is obtained by following the pointer chain to the top node. If the tree does not maintain the pointer, it is by definition its own root node. It is not necessary to maintain one set of code for tree subclasses that define the pointer and another set for classes that do not.
Another example of services implemented at the top of the inheritance hierarchy is subTrees processing. SubTrees are accessed from a message send rather than from an instance variable. This enables support for services such as the traditional enumerating methods offered by collections. All that is required is that each tree class be able to respond to the subTrees selector.
Some instance variables, such as the superTree pointer and value variable, are introduced several times by different subclasses in the inheritance hierarchy. The only code that must be duplicated among these classes is the basic read and write methods in the ''private accessing'' protocol. Other instance variables such as ''subTrees'' and ''key'' introduce considerable functionality and need many methods to support their semantics. The inheritance hierarchy is arranged so that each of these is introduced in only one subclass. Their supporting methods therefore do not need to be duplicated in other subclasses.
(6-7) Introduction of and access to instance variables
These are introduced into the tree classes as follows. The classes marked as concrete/abstract can/cannot be instantiated because they do/do not define how to access subtrees or how to distinguish leaves from branches.
TreeLW () "abstract"
PTreeLW (''superTree'') "abstract"
PVTreeLW (''value'') "abstract"
STreeLW (''subTrees'') "concrete"
SKTreeLW (''key'') "concrete"
SKPTreeLW (''superTree'') "concrete"
SKPVTreeLW (''value'') "concrete"
SKVTreeLW (''value'') "concrete"
SPTreeLW (''superTree'') "concrete"
SPVTreeLW (''value'') "concrete"
SVTreeLW (''value'') "concrete"
VTreeLW (''value'') "abstract"
BinaryTreeLW (''left'' ''right'') "concrete: defined for pedagogical purposes only"
Naming Convention
Prepend the first letter of each variable''s name to TreeLW. ''P'' designates superTree since ''S'' is already used to designate subTrees.
SubTrees and key are introduced in one class each, superTree in three classes, and value in six classes. Each is only introduced when needed, and all possible combinations are available for defining application specific subclasses. The exception is that there are no classes defining a key without subTrees because it would make no sense. The reason will become clear below.
Nil may not be stored in these variables. It is a reserved value returned by accessor methods to indicate that an instance variable has not been defined. For example, if superTree (has/has not) been defined, its accessor method will return a (non-nil/nil) value.
Here''s an explanation of the instance variables introduced by tree subclasses.
superTree
Trees that need to maintain pointers to their parent nodes do so by defining a superTree variable. Because this pointer is maintained automatically, there is no public method for setting it. Trees not needing this pointer do not define it. This saves the memory occupied by an instance variable. More significantly, when there is no superTree pointer, a single instance can be attached to and shared by several supertrees. This can save substantial memory in applications that have large numbers of trees with common substructure.
subTrees
This is a collection holding the immediate descendants of a node in the tree. Any hierarchical data structure must have a way to represent descendant nodes. In our scheme, a concrete tree class must either define subTrees as an explicit instance variable, or it must define other variables which serve the same purpose. BinaryTreeLW is an example of this alternate definition. Its class comment explains how it works. Classes not defining a subTrees variable or its equivalent are abstract. Subtrees are explained further in the next numbered section.
key, value
Data may be stored at a tree node in a key or a value. Key is used when the data is unique. It is analogous to a dictionary key in Smalltalk or to a unique key in a database. It forms the basis for traversing the tree. Value is used when the data is not unique and will not be used for traversal. A tree representing a file system is an example of a key based tree. Directories are branches and files are leaves. Within a directory, the name if each file and subdirectory is unique. These names can be used as keys. An example of a value based tree would be a parse tree representing the noun phrase ''a cold juicy apple.'' The values stored in its subTrees are lexical categories (article adjective adjective noun) and are not unique. It is also possible to define a tree class with both a key and a value. In representing a file system, the key could be the file''s name and the value its contents or attributes.
If an application uses trees with keys, i.e., SKTreeLW or a subclass, it is responsible for maintaining the keys'' uniqueness. Although SKTreeLW could be made to enforce it, there would be a performance penalty. The next section explains different ways to store subTrees. If the application uses a sequenceable collection, it must guarantee keys'' uniqueness. If it uses a set, uniqueness will be automatically guaranteed. In the comparison protocol for SKTreeLW, equality, precedence, and hash are based on the key alone. Subclasses should not redefine these to depend on other variables.
(8) Flexible representation of subtrees
Any scheme for defining a tree needs some way to represent its descendants. Two techniques are available. One may define either application specific instance variables holding the descendants or a subTrees variable holding an explicit collection. The first technique is illustrated in the BinaryTreeLW class, which is defined solely for illustrative purposes. The second technique is used in STreeLW and its subclasses.
A novel feature of STreeLW is that the client application may choose what kind of collection to use for holding subtrees. For STreeLW, some sequenceable collections are allowed. For SKTreeLW, Sets are also available. Browse implementors of validateSubTreesClass: for details. This method gives guidelines if you wish to create a new kind of collection class for holding subTrees.
In most applications, all the nodes in a tree will use the same kind of collection for storing subtrees, but this is not required. For example, it is possible for some nodes to use an ordered collection and for others to use a set. Highlight and inspect this legal code: "| t1 t2 | t1 := SKTreeLW key: 1 subTrees: OrderedCollection. t2 := SKTreeLW key: 2 subTrees: Set. t1 add: t2. t1".
It is also possible to mix instances of different tree classes. To be compatible they must both define a superTree pointer or both not define it. Highlight and inspect this legal code: "| t1 t2 | t1 := STreeLW new. t2 := SKTreeLW key: 2. t1 add: t2. t1". Highlight and evaluate this illegal code: "| t1 t2 | t1 := SPTreeLW new. t2 := SKTreeLW key: 2. t1 add: t2. t1".There is protocol for converting from one subtrees collection class to another and from one tree class to another.
Choosing a collection class may preclude the use of some methods in the accessing protocol. Trees built with sets cannot use atIndex: and atIndex:put:. Trees built with sorted collections cannot use atIndex:put:. Otherwise there are no restrictions. Trees built with arrays can use the adding and removing protocol even though arrays normally cannot.
By supporting a variety of collection classes for subtrees, STreeLW makes a typical Smalltalk tradeoff of increased flexibility at the expense of slightly decreased safety. This may offend the sensibilities of programmers who like strong typing.
Clients of a tree may communicate with its subtrees. For example,
| tree subs last |
tree := (some code defining a tree).
subs := tree subTrees.
last := subs last.
Two warnings must be heeded when doing this: (1) The collection must be able to understand the message. For example, <Array last> makes sense but <Set last> does not. (2) Access messages that read from the collection, such as <subs last>, are acceptable. Access messages that write to it, such as <subs add:> are not, since this would bypass TreeLW''s validation and pointer management mechanisms.
TreeLW subclasses must provide a means to distinguish branch nodes from leaf nodes. STreeLW bases the distinction on the contents of the subTrees variable. Branches use a collection instance and leaves use a collection class. This technique has two advantages over representing leaves by an empty collection. It is more space efficient and it allows a branch to hold zero subtrees. This is analogous to an empty directory in a file system. The technique''s advantage over defining new classes to represent leaves is that it avoids a major proliferation of the class hierarchy.
(*) Final comments and warnings
Trees may not be cyclic, i.e., you may not store a tree as a direct or recursive subtree of itself. Clients of TreeLW are responsible for observing this constraint. If they do not, infinite recursion will occur for many operations. It would impact performance too much for TreeLW to enforce it.
Subclasses that add instance variables to TreeLW other than those listed below may need to redefine <TreeLW basicCopy:>. This is somewhat like redefining copyEmpty: for new collection subclasses.
Class Variables
several <Signal> There are several signals that get raised on error conditions.
Instance Variables introduced by subclasses (nil values are illegal as explained above)
subTrees <Coll of trees A collection instance (possibly empty) is used for a branch node.
or Coll class> A collection class is used for a leaf node.
superTree <TreeLW | nontree> A non tree value marks a root node.
key <Object> Unique data stored at node; used for traversing tree.
value <Object> Non unique data stored at node. May be used to supplement key.'!
!TreeLW methodsFor: 'accessing simple'!
key
"Return the key if it is defined or nil otherwise."
^self basicKey!
key: aKey
"Validate the argument and, if the receiver defines a key, set it. Return the receiver."
self validateKey: aKey.
self basicKey: aKey!
subTrees
"Return the subTrees. The basicSubTrees method explains the returned value."
^self basicSubTrees!
subTrees: subTreesColl
"Validate the argument and set the subTrees to it. Return the receiver. The
basicSubTrees: method explains the argument."
self validateSubTrees: subTreesColl.
self definesSuperTree ifTrue: [self do: [:tree | tree makeRoot]].
self fastSubTrees: subTreesColl!
superTree
"Return the superTree if it is defined or nil otherwise."
^self basicSuperTree!
superTree: aTree
"The superTree pointer, if defined by the receiver, is managed internally and is
not modifiable by clients."
self shouldNotImplement!
value
"Return the value if it is defined or nil otherwise."
^self basicValue!
value: anObject
"Validate the argument and, if the receiver defines a value, set it. Return the receiver."
self validateValue: anObject.
self basicValue: anObject! !
!TreeLW methodsFor: 'accessing misc'!
fullPathNodes
"Return an array containing nodes from the root to the receiver, inclusive of
both. If the receiver is a root node, the array will contain the receiver as its
"Return a tree illustrating how the nodes may be of various tree types and how
the subtrees collections may be of various collection types."
"TreeLW example6"
| t u v |
t := STreeLW key: 1 subTrees: Array.
u := SKTreeLW key: 2 subTrees: Set.
v := SKVTreeLW key: 3 value: 33 subTrees: SortedCollection.
t add: u; add: v.
^t!
example7
"See also the example for BinaryTreeLW."
"BinaryTreeLW example"! !
TreeLW subclass: #STreeLW
instanceVariableNames: 'subTrees '
classVariableNames: ''
poolDictionaries: ''
category: 'Public Domain-Trees'!
STreeLW comment:
'This concrete class adds the ''subTrees'' variable to its superclass as explained in TreeLW. The ''S'' in the name comes from the ''s'' in subTrees. STreeLW adds support for
indexed tree accessing (subTrees must be a sequenceable collection)
adding and removing trees
distinguishing between branches and leaves
selecting trees
converting between leaves and branches
converting to a different collection class for holding subTrees.'!
!STreeLW methodsFor: 'accessing simple'!
subTrees
"Return the subtrees, reporting an empty collection for a leaf node."
^self isLeaf
ifTrue: [self basicSubTrees new]
ifFalse: [self basicSubTrees]! !
!STreeLW methodsFor: 'accessing misc'!
atIndex: integer
"Return the subTree at the specified index. The subTrees collection must
understand at:. Raise an error exception if the index is invalid."
^self subTrees at: integer!
atIndex: integer put: aTree
"Put aTree at the specified index in the subTrees collection and answer aTree.
The collection must understand at: and at:put:. Raise an error exception if the
index is invalid. Although you can send add: to a leaf, you cannot send at:put:."
self validateTree: aTree.
(self atIndex: integer) makeRoot.
aTree attachTo: self.
^self subTrees at: integer put: aTree! !
!STreeLW methodsFor: 'adding'!
add: aTree
"Add aTree to the subTrees collection and answer aTree. If the receiver is a leaf,
coerce it to a branch before adding to it."
self validateTree: aTree.
aTree attachTo: self makeBranch.
^self subTrees addLW: aTree!
addAll: collOfTrees
"Add collOfTrees to the receiver and answer collOfTrees. Applications working
with large sorted collections of keyed trees may want to optimize this method for
speed. See SortedCollection>>addAll:."
collOfTrees do: [:tree | self add: tree].
^collOfTrees! !
!STreeLW methodsFor: 'removing'!
detach
"Detach the receiver from its supertree, if it has one, and make it a root node.
If it is already a root node, do nothing. Return the receiver."
'This concrete class adds the ''key'' variable to its superclass as explained in TreeLW. The ''SK'' in the name comes from the ''s'' in subTrees and the ''k'' in key. SKTreeLW adds support for
access to a subtree based on its key or path
comparison of two trees based on their keys
adding and removing a subtree based on its key or path
tests based on the key or path
printing operations based on the path
other key and path based operations.
A path is a sequenceable collection of keys and is analogous to a directory path in a filesystem.
Adding a key variable also enables the use of sets and sorted collections for storing subTrees. The key is used to find a tree in a set and to compare two trees in a sorted collection. Methods in the comparing protocol must be based on the key alone.'!
!SKTreeLW methodsFor: 'accessing misc'!
atInclusivePath: aPath
"Same as atInclusive:ifAbsent:, but does default error handling."
^self atInclusivePath: aPath ifAbsent: [self class badPathSignal raise]!
atInclusivePath: aPath ifAbsent: aBlock
"Return the tree at aPath starting from the receiver. This path is a sequenceable
collection of keys inclusive of the receiver and inclusive of the last node. Return
"Same as rootFromPath: except that the last node on the path is returned."
| root |
root := self key: aPath first.
^(root addPath: (aPath copyFrom: 2 to: aPath size)) value!
rootFromPath: aPath
"Create and return a new instance containing nodes along aPath. The path is a
non empty sequenceable collection of keys starting from the new root node.
Return the resulting root node."
| root |
root := self key: aPath first.
root addPath: (aPath copyFrom: 2 to: aPath size).
^root! !
!SKTreeLW class methodsFor: 'examples'!
readMe
"TreeLW contains examples for this class."! !
SKTreeLW subclass: #SKPTreeLW
instanceVariableNames: 'superTree '
classVariableNames: ''
poolDictionaries: ''
category: 'Public Domain-Trees'!
SKPTreeLW comment:
'This concrete class adds the ''superTree'' variable to its superclass as explained in TreeLW. The ''SKP'' in the name comes from the ''s'' in subTrees, the ''k'' in key and the ''p'' in superTree.'!
!SKPTreeLW methodsFor: 'private accessing'!
basicSuperTree
"Return the contents of the superTree variable. Do not redefine in subclasses."
^superTree!
basicSuperTree: aTree
"Set the superTree variable to aTree and return the receiver. If the argument is a
tree, it becomes the superTree of the receiver. If the argument is something
else (except nil, which is not allowed), the receiver becomes a root node. Do not
'This concrete class adds the ''value'' variable to its superclass as explained in TreeLW. The ''SKPV'' in the name comes from the ''s'' in subTrees, the ''k'' in key, the ''p'' in superTree and the ''v'' in value.'!
!SKPVTreeLW methodsFor: 'private accessing'!
basicValue
"Return the contents of the value variable. Do not redefine in subclasses."
^value!
basicValue: anObject
"Set the value variable to anObject and return the receiver. Do not redefine in
'This concrete class adds the ''value'' variable to its superclass as explained in TreeLW. The ''SKV'' in the name comes from the ''s'' in subTrees, the ''k'' in key and the ''v'' in value.'!
!SKVTreeLW methodsFor: 'private accessing'!
basicValue
"Return the contents of the value variable. Do not redefine in subclasses."
^value!
basicValue: anObject
"Set the value variable to anObject and return the receiver. Do not redefine in
'This concrete class adds the ''superTree'' variable to its superclass as explained in TreeLW. The ''SP'' in the name comes from the ''s'' in subTrees and the ''p'' in superTree.'!
!SPTreeLW methodsFor: 'private accessing'!
basicSuperTree
"Return the contents of the superTree variable. Do not redefine in subclasses."
^superTree!
basicSuperTree: aTree
"Set the superTree variable to aTree and return the receiver. If the argument is a
tree, it becomes the superTree of the receiver. If the argument is something
else (except nil, which is not allowed), the receiver becomes a root node. Do not
'This concrete class adds the ''value'' variable to its superclass as explained in TreeLW. The ''SPV'' in the name comes from the ''s'' in subTrees, the ''p'' in superTree and the ''v'' in value.'!
!SPVTreeLW methodsFor: 'private accessing'!
basicValue
"Return the contents of the value variable. Do not redefine in subclasses."
^value!
basicValue: anObject
"Set the value variable to anObject and return the receiver. Do not redefine in
'This concrete class adds the ''value'' variable to its superclass as explained in TreeLW. The ''SV'' in the name comes from the ''s'' in subTrees and the ''v'' in value.'!
!SVTreeLW methodsFor: 'private accessing'!
basicValue
"Return the contents of the value variable. Do not redefine in subclasses."
^value!
basicValue: anObject
"Set the value variable to anObject and return the receiver. Do not redefine in
'This abstract class adds the ''superTree'' variable to its superclass as explained in TreeLW. The ''P'' in the name comes from the ''p'' in superTree.'!
!PTreeLW methodsFor: 'private accessing'!
basicSuperTree
"Return the contents of the superTree variable. Do not redefine in subclasses."
^superTree!
basicSuperTree: aTree
"Set the superTree variable to aTree and return the receiver. If the argument is a
tree, it becomes the superTree of the receiver. If the argument is something
else (except nil, which is not allowed), the receiver becomes a root node. Do not
'This abstract class adds the ''value'' variable to its superclass as explained in TreeLW. The ''PV'' in the name comes from the ''p'' in superTree and the ''v'' in value.'!
!PVTreeLW methodsFor: 'private accessing'!
basicValue
"Return the contents of the value variable. Do not redefine in subclasses."
^value!
basicValue: anObject
"Set the value variable to anObject and return the receiver. Do not redefine in
'A BinaryTreeLW is a concrete class defined for pedagogic purposes as a tree whose branch nodes have two subtrees and whose leaf nodes have none. It provides an example of how to define a TreeLW subclass that lacks a subTrees variable.
Another implementation technique would be to define a new collection class that holds the two nodes. However, that would take 20 bytes more per node for ST80 4.1 than the technique used here.
If one wished to use less memory than the current technique, one could define separate classes for branches and leaves. Leaves would not have ''left'' or ''right'' instance variables. However, that would make it harder to design subclasses of binary trees.
BinaryTreeLW is a subclass of VTreeLW. If one wanted to define a binary tree that maintained a superTree pointer, it would be a subclass of PVTreeLW. The superclass would maintain the pointer automatically and no extra code would be required in BinaryTreeLW. See the left:right: method for further comments.
A BTree or BalancedTree could be defined in a manner similar to BinaryTreeLW.
Instance Variables
(value) <Object (not nil)> (Inherited): The object stored at a node.
left <TreeLW | nil> The left subtree for a branch node; nil for a leaf node.
right <TreeLW | nil> The right subtree for a branch node; nil for a leaf node.'!
!BinaryTreeLW methodsFor: 'accessing simple'!
left
"Return the left node if the receiver is a branch or nil if it is a leaf."
^left!
left: tree1 right: tree2
"Set the two nodes and return the receiver. To make the receiver a leaf node,
use subTrees: Array new.
Implementation note: this is based on the subTrees: method to take advantage
of that method's argument validation. If BinaryTreeLW had been defined as a
subclass of PVTreeLW, using subTrees: would also take advantage of its
automatic management of the superTree pointer."
self subTrees: (Array with: tree1 with: tree2)!
right
"Return the right node if the receiver is a branch or nil if it is a leaf."
^right! !
!BinaryTreeLW methodsFor: 'testing misc'!
isLeaf
"Return a boolean indicating whether the receiver is a leaf node.
Implementation note: we do not need to test the right node because either both
are trees or both are nil."
^self left isNil! !
!BinaryTreeLW methodsFor: 'private initializing'!
defaultSubTrees
"Return the default value for initializing the subTrees."
^Array new! !
!BinaryTreeLW methodsFor: 'private accessing'!
basicSubTrees
"Return an array containing the subtrees."
^self isLeaf
ifTrue: [Array new]
ifFalse: [Array with: self left with: self right]!
basicSubTrees: seqColl
"Set the left and right nodes from seqColl, assuming it is a sequenceable
collection of zero or two trees. Return the receiver."
seqColl isEmpty
ifTrue:
[left := nil.
right := nil]
ifFalse:
[left := seqColl at: 1.
right := seqColl at: 2]! !
!BinaryTreeLW methodsFor: 'private validating'!
validateSubTreesCollection: aCollection
"Raise an exception if aCollection is invalid. It must be empty or contain exactly
'(1) PUBLIC DOMAIN FILEIN COMMENTS (same as TreeLW)
(2) NORMAL CLASS COMMENTS
Class TesterLW is used to verify the correctness of the class and instance methods in another class. It is designed for testing back end calculation and storage classes such as numbers and collections, but is less suitable for testing user interface classes. An example will serve to explain its usage.
Suppose you want to verify the class TreeLW. TreeLW''s test suite will be called TesterTreeLW and will be a subclass of TesterLW. The methods in the test suite will have the same names as the methods in TreeLW. Each test method will have block(s) of code designed by the programmer to exercise the corresponding method in TreeLW. TesterLW evaluates the blocks and compares the results with expected results. The test for this method passes if all compare and fails otherwise.
Normally you will want to test a method''s response both to error conditions and to normal conditions. If you fill a block with code designed to raise an exception, TesterLW will confirm that the expected error actually occurred. If you fill a block with code designed to generate data, TesterLW will confirm that the correct data got generated. In the two respective cases, a string representing the error or a string representing the data is compared with an expected string.
Now let''s go through the steps for setting up and running a test suite for TreeLW and its subclasses.
(1) Define TesterForTreesLW along with the leaf nodes in the class hierarchy shown below. In other applications the class analogous to TesterForTreesLW may not be necessary. See its class comment for why it is needed here.
TesterLW ()
TesterForTreesLW ()
TesterBinaryTreeLW ()
TesterPTreeLW ()
TesterPVTreeLW ()
TesterSKPTreeLW ()
TesterSKPVTreeLW ()
TesterSKTTreeLW ()
TesterSKVTTreeLW ()
TesterSPTTreeLW ()
TesterSPVTreeLW ()
TesterSTreeLW ()
TesterSVTreeLW ()
TesterTreeLW ()
TesterVTreeLW ()
(2) Create method stubs for these classes by evaluating
classes do: [:class | TesterLW new createStubsFor: class].
The list of classes could be replaced by <TreeLW withAllSubclasses> if you don''t have any application specific subclasses of TreeLW which you wish to exclude from the tests.
(3) Edit the stubs to fill them with test code. This is where the bulk of the work lies. Use the TesterTreeLW methods as examples.
(4) There will probably remain some stubs you didn''t edit because there was nothing interesting to test. Remove them by evaluating
classes do: [:class | TesterLW new removeStubsFor: class].
The list of classes could be replaced by <TreeLW withAllSubclasses> if you don''t have any application specific subclasses of TreeLW which you wish to exclude from the tests.
(5) Run the tests by evaluating the code below and viewing the results in the System Transcript.
TesterForTreesLW new runAllSubclasses.
Because the methods in a test suite use the same names as the methods they''re verifying, they can be cross referenced by the system browser using ''implementors'' as well as ''senders''. A programmer learning a new class can search its test suite for examples of idiomatic usage. An individual test can be run by highlighting and evaluating its code to observe the performance of the method it is verifying.
Shortcomings of this technique: (1) We are assuming the test results can be characterized by a string. This is too simplistic for some situations. In particular, the technique is not suited for testing methods implementing user interface logic or methods that interact heavily with some other subsystem. (2) The strings will be very dependent on error messages and on printing protocols. The test methods will require updating whenever an error message or print format is changed. (3) We generate testing stubs for those methods directly defined by a class, but not for those inherited by a class. A programmer wishing to test inherited methods will have to write the test method from scratch.
The following cannot be instance variables because they must be accessable from class methods.
Class Variables
ErrorBlockCount <Integer> Number of blocks of error raising code executed during a test run.
DataBlockCount <Integer> Number of blocks of data generating code executed during a test run.
'!
!TesterLW methodsFor: 'public'!
createStubsFor: testeeClass
"Create class and instance method stubs for testing testeeClass. Preserve
intact any test methods that already exist. Also add a class comment if one
